//
// Created by zhou on 2021/10/31.
//
#include <vector>
#include <iostream>
#include "algorithm"
using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int cow=triangle.size();
        vector<vector<int>> result(cow);
        if(cow==1)return triangle[0][0];
        result[0]={triangle[0][0]};
        for(int i=1;i<cow;i++){

            result[i].resize(i+1);
            for(int j=0;j<=i;j++){
                if(j==0){
                    result[i][j]=result[i-1][j]+triangle[i][j];
                }
                else if(j==i){
                    result[i][j]=result[i-1][j-1]+triangle[i][j];
                }
                else{
                    result[i][j]=min(result[i-1][j]+triangle[i][j], result[i-1][j-1]+triangle[i][j]);
                }
            }
        }
        return *min_element(result[cow-1].begin(),result[cow-1].end());
    }
};
int main(){
    vector<vector<int>> matrix={
            {2},
            {2,1},
            {3,4,5},
            {10,-1,2},
            {4,1,4,6}
    };
    Solution solution;
    cout<<solution.minimumTotal(matrix);
}
